package _17_剑指Offer;

public class _39_剑指Offer数组中出现次数超过一半的数字 {

    public static void main(String[] args) {

        _39_剑指Offer数组中出现次数超过一半的数字 v = new _39_剑指Offer数组中出现次数超过一半的数字();

        int[] ins = new int[]{1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6};
        System.out.println(v.majorityElement(ins));

    }

    // 摩尔投票， 对次数计数
    public int majorityElement(int[] nums) {
        int count = 0;
        int num = 0;
        for (int j : nums) {
            if (count == 0) {
                count = 1;
                num = j;
            } else if (num == j) {
                count++;
            } else {
                count--;
            }
        }
        return num;
    }

    public int majorityElement2(int[] nums) {
        int count = 0;
        int num = 0;
        for (int cur : nums) {
            if (count == 0) {
                num = cur;
                count++;
            } else if (cur == num) {
                count++;
            } else {
                count--;
            }
        }
        return num;
    }

    public int majorityElement1(int[] nums) {
        int num = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 1 && nums[i] != num) {
                num = nums[i];
            } else if (nums[i] == num) {
                count++;
            } else {
                count--;
            }
        }
        return num;
    }

}
